package com.ding.practice.algorithm.leetcode.hot100;

import java.util.TreeSet;

/**
 * 力扣热题100之最大连续数组和
 * @ID = 53
 * @date 2024年07月18日15:54:51
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组
 * 是数组中的一个连续部分。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 *
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 */
public class MaxSubArray_53 {

    public static int maxSubArray(int[] nums) {
        // 前缀和+hash求解，这怎么和上个题好像啊啊啊

        int ret = nums[0];
        int sum = nums[0];
        // 注意从1开始遍历
        /*
         思想：从左到右，要想求全部的最大连续解，可以从第n个开始，求前n个中的最大连续解，然后求n+1的最大连续解，
         这个时候就要将前n个的最大解加上n+1,和前n个最大解做比较，谁大取谁

         */
        for(int i = 1;i < nums.length; i++){
            sum = Math.max(sum + nums[i], nums[i]);
            ret = Math.max(ret,sum);
        }
        return ret;

    }


    /*
    第一次的解法，前缀和+排序树，最大值 = 当前前缀和-之前的最小前缀和
     */
    public static int maxSubArray2(int[] nums) {
        // 前缀和+hash求解，这怎么和上个题好像啊啊啊
        TreeSet<Integer> preSumSet = new TreeSet();
        int ret = -99;
        int sum = 0;
        preSumSet.add(0);
        for(int i =0;i < nums.length; i++){
            sum = sum + nums[i];
            int maxSubArray = sum - preSumSet.first();
            if(i == 0){
                ret = nums[i];
            }
            if(maxSubArray > ret){
                ret = maxSubArray;
            }
            preSumSet.add(sum);
        }
        return ret;

    }

    public static void main(String[] args) {
        int[] p = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(p));
    }
}
